package com.study.lu;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 花期内花的数目
 *
 * @author raoLuPing
 * @date 2022/08/11 19:33
 **/
public class 花期内花的数目 {
    /**
     * 给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。
     * <p>
     * 请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * <p>
     * 输入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
     * 输出：[1,2,2,2]
     * 解释：上图展示了每朵花的花期时间，和每个人的到达时间。
     * 对每个人，我们返回他们到达时在花期内花的数目。
     * 示例 2：
     * <p>
     * <p>
     * <p>
     * 输入：flowers = [[1,10],[3,3]], persons = [3,3,2]
     * 输出：[2,2,1]
     * 解释：上图展示了每朵花的花期时间，和每个人的到达时间。
     * 对每个人，我们返回他们到达时在花期内花的数目。
     *  
     * <p>
     * 提示：
     * <p>
     * 1 <= flowers.length <= 5 * 104
     * flowers[i].length == 2
     * 1 <= starti <= endi <= 109
     * 1 <= persons.length <= 5 * 104
     * 1 <= persons[i] <= 109
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/number-of-flowers-in-full-bloom
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param args
     * @author raoLuPing
     * @date 2022/8/11 19:34
     */
    public static void main(String[] args) {
//        int[][] flowers = new int[][]{{1, 6}, {3, 7}, {9, 12}, {4, 13}};
//        int[] persons = new int[]{
//                2, 3, 7, 11
//        };

        int[][] flowers = new int[][]{{1, 10}, {3, 3}};
        int[] persons = new int[]{
                3, 3, 2
        };
        int[] ints = fullBloomFlowers4(flowers, persons);
        System.out.println(Arrays.stream(ints).mapToObj(v -> String.valueOf(v)).collect(Collectors.joining(",")));

        System.out.println(find(Arrays.asList(3, 3, 3, 3), 4));
    }

    /**
     * 超了内存限制。因为存了很多不需要的结果
     *
     * @param flowers
     * @param persons
     * @return int[]
     * @author raoLuPing
     * @date 2022/8/12 10:06
     */
    public static int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        Map<Integer, Integer> resultMap = new HashMap<>(16);

        for (int i = 0; i < flowers.length; i++) {
            for (int j = flowers[i][0]; j <= flowers[i][1]; j++) {
                int idx = j;
                Integer integer = resultMap.get(idx);
                if (integer == null) {
                    integer = 0;
                }
                if (flowers[i][0] <= idx || flowers[i][1] >= idx) {
                    integer += 1;
                }
                resultMap.put(idx, integer);
            }

        }
        int[] results = new int[persons.length];

        for (int i = 0; i < persons.length; i++) {
            results[i] = null == resultMap.get(persons[i]) ? 0 : resultMap.get(persons[i]);
        }

        return results;
    }

    /**
     * 超了内存限制。因为存了很多不需要的结果
     * 改进版，但是时间还是超了
     *
     * @param flowers
     * @param persons
     * @return int[]
     * @author raoLuPing
     * @date 2022/8/12 10:06
     */
    public static int[] fullBloomFlowers2(int[][] flowers, int[] persons) {
        Map<Integer, Integer> resultMap = new HashMap<>(16);
        // 只存结果相关 数据 减少无关数据
        for (int i = 0; i < persons.length; i++) {
            resultMap.put(persons[i], 0);
        }

        for (int i = 0; i < flowers.length; i++) {
            // 但是如果 花期时间过长。 这里for循环次数太多。会超出时间限制
            for (int j = flowers[i][0]; j <= flowers[i][1]; j++) {
                int idx = j;
                Integer integer = resultMap.get(idx);
                if (integer == null) {
                    continue;
                }
                if (flowers[i][0] <= idx || flowers[i][1] >= idx) {
                    integer += 1;
                }
                resultMap.put(idx, integer);
            }

        }
        int[] results = new int[persons.length];

        for (int i = 0; i < persons.length; i++) {
            results[i] = null == resultMap.get(persons[i]) ? 0 : resultMap.get(persons[i]);
        }

        return results;
    }

    /**
     * 超了内存限制。因为存了很多不需要的结果
     * 改进版，但是时间还是超了
     *
     * @param flowers
     * @param persons
     * @return int[]
     * @author raoLuPing
     * @date 2022/8/12 10:06
     */
    public static int[] fullBloomFlowers3(int[][] flowers, int[] persons) {
        Map<Integer, Integer> resultMap = new HashMap<>(16);

        // 要保障有序。否则 person 数组中会
        List<Integer> orders = Arrays.stream(persons).sorted().boxed().collect(Collectors.toList());

        for (int i = 0; i < flowers.length; i++) {
            // 第二层改为遍历 persons
            for (int j = 0; j < orders.size(); j++) {
                if (j != 0 && orders.get(j).equals(orders.get(j - 1))) {
                    continue;
                }
                // int idx = j;
                Integer integer = resultMap.get(orders.get(j));
                if (integer == null) {
                    integer = 0;
                }
                if (flowers[i][0] <= orders.get(j) && flowers[i][1] >= orders.get(j)) {
                    integer += 1;
                }
                resultMap.put(orders.get(j), integer);
            }

        }
        int[] results = new int[persons.length];

        for (int i = 0; i < persons.length; i++) {
            results[i] = null == resultMap.get(persons[i]) ? 0 : resultMap.get(persons[i]);
        }

        return results;
    }


    /**
     * 1. f_n_start 花在第n天开始开花。那么这天新增开花数加1
     * 2. f_n_end  花在第n天开始结束开花。那么第n+1天新增开花数-1
     * 3. 所以就可以组成两个数组。一个是花开日期数组 f_start。另外一个就是 f_ends
     * 4. 那么简单了，只需要对person 进行变量。看看在不在 f_start or f_ends 中。那么问题就变成了 看看某个数是否在数组中。很明显就可以用到二分法了。
     *
     * @param flowers
     * @param persons
     * @return int[]
     * @author raoLuPing
     * @date 2022/8/12 10:06
     */
    public static int[] fullBloomFlowers4(int[][] flowers, int[] persons) {
        List<Integer> f_start_List = Arrays.stream(flowers).map(v -> v[0]).sorted().collect(Collectors.toList());
        List<Integer> f_end_List = Arrays.stream(flowers).map(v -> v[1]).sorted().collect(Collectors.toList());

        return Arrays.stream(persons)
                // 第N还有的开花数 = 第n天总开花数 - 第 n-1 天总结花数
                // 为啥实现是 n+1 代表第n天？
                // 二分法特性。不是闭区间。所以要n+1代表n
                // 示例 3,3,3  3 返回的是0。不符合题意 3+1 即返回所需的结果
                .map(n -> find(f_start_List, n + 1) - find(f_end_List, n))
                .toArray();
    }

    /**
     * 在一个有序数组中。给定一个数。求这个数的位置。这里就可以用到二分法了。
     * 1. 在开花期数组中排好序、就需要依次遍历。比大小。大于就+1。小于就说明这朵花是在当天之后开的、、也就是坐标。跟二分法类似
     *
     * @param list
     * @param i
     * @return int
     * @author raoLuPing
     * @date 2022/8/12 15:09
     */
    private static int find(List<Integer> list, int i) {
        int left = 0;
        int right = list.size();
        while (left < right) {
            Integer mid = (left + right) / 2;
            if (list.get(mid) >= i) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
